#include <stdio.h>
#include <stdlib.h>
#include "sorts.h"

#define PARENT(i) ((i)-1)/2)
#define LEFT(i)   ((i)*2+1)
#define RIGHT(i)  ((i)*2+2)
#define SWAP(T,a,b)  {T t=a; a=b; b=t; } 

//从i结点开始，做maxHeapify，这是一个递归函数
static void maxHeapify(ELE_TYPE A[],int i,int size) 
{
    int l = LEFT(i);      // i的左子结点
    int r = RIGHT(i);     // i的右子结点
    int maxNodeIdx = i;   // 值最大的那个结点的下标，初化为i
    
    if ( l<size && A[l] > A[maxNodeIdx])
        maxNodeIdx = l;

    if ( r<size && A[r] > A[maxNodeIdx])
        maxNodeIdx = r;

    if (maxNodeIdx != i)    // 最大值不是当前结点，交换之
    {
        SWAP(ELE_TYPE,A[i],A[maxNodeIdx]);
        maxHeapify(A, maxNodeIdx, size);  //继续对子结点做堆化操作，保证子树也是大顶堆
    }
}

// 使长度为n的数组A变为一个大顶堆。其时间复杂度为O(n)
static void buildMaxHeap(ELE_TYPE A[], int n)
{
    // 从最后一个非叶子节点开始，对每一个非叶子节点做maxHeapify
    int lastNonLeafNode=n/2-1;
    for (int i = lastNonLeafNode; i >= 0; i--)  
        maxHeapify(A, i, n);
}

//堆排序算法
void heap_sort(ELE_TYPE arr[], int len)  
{
    if (len<2)
        return ;

    buildMaxHeap(arr,len);  //将整个数组变成一个大顶堆
    int heapSize=len;
    do
    {
        // 将根节点(最大值)与堆的最后一个元素arr[heapSize-1]交换
        SWAP(ELE_TYPE,arr[0],arr[heapSize-1]);
        
        heapSize--;  // 堆（待排序数组）长度减一
        // 此时，arr[heapSize]变成有序数的的第一个元素

        maxHeapify(arr, 0, heapSize);  //保持堆结构
    }while (heapSize>1);
}

void test_heap_sort()
{
	ELE_TYPE arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
	int len; 
 
	printf("Original data are:");
	len = (int) sizeof(arr) / sizeof(arr[0]);
	print_array(arr, len);
 
	heap_sort(arr, len);
	printf("The data after sorted are:");
	print_array(arr, len);	
}
